# define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>

struct ListNode {
    int val;
    struct ListNode* next;
    
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* cur1 = headA, * cur2 = headB;
    int sz1 = 0, sz2 = 0;
    while (cur1->next)
    {
        cur1 = cur1->next;
        sz1++;
    }
    while (cur2->next)
    {
        cur2 = cur2->next;
        sz2++;
    }
    if (cur1 != cur2)
        return NULL;
    struct ListNode* longlist = headA, * shortlist = headB;
    if (sz1 < sz2)
    {
        longlist = headB;
        shortlist = headA;
    }
    int gap = abs(sz1 - sz2);
    while (gap--)
    {
        longlist = longlist->next;
    }
    while (longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return longlist;
}

struct ListNode* partition(struct ListNode* pHead, int x) {
    // write code here
    assert(pHead);
    struct ListNode* gGuard, * gTail, * lGuard, * lTail;
    gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    gTail->next = lTail->next = NULL;

    struct ListNode* cur = pHead;
    while (cur)
    {
        if (cur->val < x)
        {
            lTail->next = cur;
            lTail = cur;
        }
        else
        {
            gTail->next = cur;
            gTail = cur;
        }
        cur = cur->next;
    }
    lTail->next = gGuard->next;
    gTail->next = NULL;
    pHead = lGuard->next;
    free(gGuard);
    free(lGuard);
    return pHead;
}

int main()
{
    return 0;
}